package binary_heap;

import utils.AlgorithmUtil;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Heap_231105 {

    public static <T> void swap(T[] data, int a, int b) {
        T tmp = data[a];
        data[a] = data[b];
        data[b] = tmp;
    }

    /**
     * 默认按照小根堆插入元素
     */
    public static <T> void heapInsert(T[] data, int index, Comparator<T> cmp) {
        while (cmp.compare(data[index], data[parentOf(index)]) < 0) {
            swap(data, index, parentOf(index));
            index = parentOf(index);
        }
    }

    /**
     * 将index位置的元素向下堆化
     */
    public static <T> void heapify(T[] data, int index, int heapSize, Comparator<T> cmp) {
        int left = leftOf(index);
        while (left < heapSize) {
            int right = left + 1;
            int smallerChild = right < heapSize ?
                    cmp.compare(data[left], data[right]) <= 0 ? left : right
                    : left;
            if (cmp.compare(data[index], data[smallerChild]) <= 0) {
                break;
            }
            swap(data, index, smallerChild);
            index = smallerChild;
            left = leftOf(index);
        }
    }

    /**
     * 计算给定位置的左子节点索引
     */
    public static int leftOf(int index) {
        return index * 2 + 1;
    }

    /**
     * 计算给定位置的右子节点索引
     */
    public static int rightOf(int index) {
        return index * 2 + 2;
    }

    /**
     * 计算给定位置的父节点索引
     */
    public static int parentOf(int index) {
        return (index - 1) / 2;
    }

    public static class Heap<T> {
        private T[] data;
        private int size;
        private Comparator<T> cmp;

        public Heap() {
            this.data = (T[]) new Object[8];
        }

        public Heap(Comparator<T> cmp) {
            this();
            this.cmp = cmp;
        }

        public void push(T t) {
            capCheck();
            data[size] = t;
            heapInsert(data, size++, getComparator());
        }

        public T pop() {
            if (size == 0) {
                throw new IndexOutOfBoundsException("heap is empty");
            }
            swap(data, 0, --size);
            T res = data[size];
            data[size] = null; // help gc
            heapify(data, 0, size, getComparator());
            return res;
        }

        private Comparator<T> getComparator() {
            return null != this.cmp ? this.cmp : (o1, o2) -> ((Comparable<T>) o1).compareTo(o2);
        }

        public void capCheck() {
            if (size == data.length) {
                doubleCapacity();
            }
        }

        public void doubleCapacity() {
            this.data = Arrays.copyOf(data, data.length << 1);
        }

        public boolean isEmpty() {
            return size == 0;
        }
    }

    public static void main(String[] args) {
        List<Integer> data = Stream.generate(() -> new Random().nextInt(10000))
                .limit(1000)
                .collect(Collectors.toList());

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        Heap<Integer> heap = new Heap<>();
        data.forEach(item -> {
            pq.add(item);
            heap.push(item);
        });

        while (!pq.isEmpty() || !heap.isEmpty()) {
            Integer a = pq.poll();
            Integer b = heap.pop();
            if (!Objects.equals(a, b)) {
                throw new RuntimeException("shit!, " + String.format("example: %d, my: %d", a, b));
            }
        }
    }
}
